Sorting


What's Sorting?

	putting a sequence of items in order


Why is Sorting Important?

	1. people can process data better when it is sorted
		words in a dictionary
		index of a book
		card catalog in a library

	2. some algorithms can be faster when input is sorted
		binary search
		finding duplicates


How do you find duplicates in an unsorted array?

	8 2 4 1 2 4

	quadratic time

	boolean duplicates (Object[] a) {
	    for (int i = 0; i < a.length; i++)
	        for (int j = i+1; j < a.length; j++)
		    if (a[i].equals(a[j]))
		        return true;
	    return false;
	}


How do you find duplicates in a sorted array?

	1 2 2 4 4 8

	linear time



Selection Sort


How does Selection Sort work?

	keep boundary between sorted and unsorted parts
	sorted part starts empty
	find smallest item in unsorted part
	swap with first item in unsorted part
	sorted part is now larger by 1


Show each step of Selection Sort on the array.

	8 2 4 1 2 4

	|8 2 4 1 2 4
	 1|2 4 8 2 4
	 1 2|4 8 2 4
	 1 2 2|8 4 4
	 1 2 2 4|8 4
	 1 2 2 4 4|8


void selectionSort (Comparable[] a) {
    for (int i = 0; i < a.length-1; i++) {
	int min = i;
	for (int j = i+1; j < a.length; j++)
	    if (a[j].compareTo(a[min]) < 0)
	       min = j;
	Comparable tmp = a[min];
	a[min] = a[i];
	a[i] = tmp;
    }
}



What's a compare?


What's a swap?


What kind of input is worst-case for Selection sort?

	doesn't matter


How many compares? (for Selection sort on any input)

	O(n^2)


How many swaps? (for Selection sort on any input)

	O(n)


DEMO	(selection sort running time on sorted, reverse, random data)



Insertion Sort


How does Insertion Sort work?

	keep boundary between sorted and unsorted parts
	sorted part starts with first item
	take first item in unsorted part and insert into sorted part
	sorted part is now larger by 1


Show each step of Insertion Sort on the array.

	8 2 4 1 2 4

	8|2 4 1 2 4
	2 8|4 1 2 4
	2 4 8|1 2 4
	1 2 4 8|2 4
	1 2 2 4 8|4
	1 2 2 4 4 8


void insertionSort (Comparable[] a) {
    for (int p = 1; p < a.length; p++) {
        Comparable tmp = a[p];
	int j;
	for (j = p; j > 0 && tmp.compareTo(a[j-1]) < 0; j--)
	    a[j] = a[j-1];
	a[j] = tmp;
    }
}


What kind of input is worst-case for insertion sort?

	reverse sorted input


How many compares? (for insertion sort on reverse-sorted input)

	O(n^2)


How many swaps? (for insertion sort on reverse-sorted input)

	O(n^2)


What kind of input is best-case for insertion sort?

	sorted input


How many compares? (for insertion sort on sorted input)

	O(n)


How many swaps? (for insertion sort on sorted input)

	none



How does Insertion Sort perform on random input?


How many compares? (for insertion sort on random input)

	O(n^2)


How many swaps? (for insertion sort on random input)

	O(n^2)


DEMO	(insertion sort running time on sorted, reverse, random data)



Bubble Sort


How does Bubble Sort work?

	pass over array N times
	each time bubble the largest value to the end
	compare adjacent elements
	swap adjacent elements if needed


Show each step of bubble sort on the array.

	8 2 4 1 2 4

	8 2 4 1 2 4
	2 4 1 2 4 8
	2 1 2 4 4 8
	1 2 2 4 4 8

	8 4 4 2 2 1

	8 4 4 2 2 1
	4 4 2 2 1 8
	4 2 2 1 4 8
	2 2 1 4 4 8
	2 1 2 4 4 8
	1 2 2 4 4 8


void bubbleSort (Comparable[] a) {
    for (int i = 0; i < a.length; i++) {
	for (int j = 0; j < a.length-1; j++) {
	    if (a[j].compareTo(a[j+1]) > 0) {
	        Comparable tmp = a[j];
		a[j] = a[j+1];
		a[j+1] = tmp;
	    }
	}
    }
}



What kind of input is worst-case for bubble sort?

	reverse sorted input


How many compares? (for bubble sort on reverse-sorted input)

	O(n^2)


How many swaps? (for bubble sort on reverse-sorted input)

	O(n^2)


What kind of input is best-case for bubble sort?

	sorted input


How many compares? (for bubble sort on sorted input)

	O(n^2)


How many swaps? (for bubble sort on sorted input)

	none



How does Bubble Sort perform on random input?


How many compares? (for bubble sort on random input)

	O(n^2)


How many swaps? (for bubble sort on random input)

	O(n^2)


DEMO	(bubble sort running time on sorted, reverse, random data)